package seqlist.oj;

/**
 * @Author: yuisama
 * @Date: 2019/12/9 13:01
 * @Description:相交链表-裁剪法
 * https://leetcode-cn.com/problems/intersection-of-two-linked-lists/
 */
public class Solution160 {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode tempA = headA;
        ListNode tempB = headB;
        int countA = 0;
        int countB = 0;
        while (tempA != null) {
            tempA = tempA.next;
            countA ++;
        }
        while (tempB != null) {
            tempB = tempB.next;
            countB ++;
        }
        // 裁剪A
        while (countA > countB) {
            headA = headA.next;
            countA--;
        }
        // 裁剪B
        while (countB > countA) {
            headB = headB.next;
            countB --;
        }
        // 此时A与B长度一致，从头开始一起走，相交的话中途会相遇
        while (headA != null) {
            if (headA == headB) {
                return headA;
            }else {
                headA = headA.next;
                headB = headB.next;
            }
        }
        // 走完若还未相遇则不想交
        return null;
    }
}
